package com.caoyanan.algorithm.question.zuoTraining.training004.class02;

/**
 * 矩阵去回
 *
 * 给定一个矩阵matrix，先从左上角开始，每一步只能往右或者往下走，走到右下角。
 * 然后从右下角出发，每一步只能往上或者往左走，再回到左上角。
 * 任何一个位置的数字，只能获得一遍。返回最大路径和。
 *
 * @author: caoyanan
 * @time: 2021/6/4 4:07 下午
 */
public class Question02_MatrixGoAndBack {

    public static void main(String[] args) {

        int[][] matrix = {
                { 1, 1, 1, 1, 1, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                { 1, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 1, 1, 1 } };
        Integer[][][] dp = new Integer[matrix.length][matrix[0].length][matrix.length];
        System.out.println(process(matrix, 0, 0, 0, dp));
    }

    /**
     * 一个矩阵，一个人从左上角走到右下角，然后再回来，一个节点最多经过一次(经过多次后只能算一次节点权重值)，求最大路径和
     *
     * 遇到矩阵，求路径相关的，都是递归，很少能改成动态规划，因为依赖的位置太杂乱了，上下左右走
     * 这道题想成两个人，都从左上角出发到右下角，
     * 那么当前加入a走到了(rowA, columnA)点， B一定就走到了(rowB, rowA+columnA-rowB)点，所以记忆化搜索就是一个三维的数组
     * 然后，a往右b往右，a往下b往下，a往右b往下，a往下往右，就这四种情况(往上走或者往左走就会绕圈圈无限循环了)
     *
     * @param arr
     * @param dp
     * @return
     */
    private static int process(int[][] arr, int rowA, int columnA, int rowB, Integer[][][] dp) {

        int columnB = rowA + columnA - rowB;
        if (rowA > arr.length - 1
                || columnA > arr[rowA].length - 1
                || rowB > arr.length - 1
                || columnB > arr[rowB].length - 1) {
            return Integer.MIN_VALUE;
        }
        if (dp[rowA][columnA][rowB] != null) {
            return dp[rowA][columnA][rowB];
        }
        if (rowA == arr.length - 1 && columnA == arr[0].length - 1) {
            dp[rowA][columnA][rowB] = arr[rowA][columnA];
            return dp[rowA][columnA][rowB];
        }


        //A往右，B往右
        int aRightBRight = process(arr, rowA, columnA + 1, rowB, dp);
        //A往下，B往下
        int aBottomBBottom = process(arr, rowA + 1, columnA, rowB + 1, dp);
        //A往右，B往下
        int aRightBBottom = process(arr, rowA, columnA + 1, rowB + 1, dp);
        //A往下，B往右
        int aBottomBRight = process(arr, rowA + 1, columnA, rowB, dp);

        int next = Math.max(
                Math.max(aRightBRight, aRightBBottom),
                Math.max(aBottomBBottom, aBottomBRight));
        int bValue = arr[rowB][columnB];
        if (rowA == rowB) {
            bValue = 0;
        }
        dp[rowA][columnA][rowB] = next + arr[rowA][columnA] + bValue;
        return dp[rowA][columnA][rowB];
    }
}
